package lc20240601;

import lc20240521.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class AVGBinaryTree {
    public static void main(String[] args) {

        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(3);
        System.out.println(averageOfLevels1(root));
    }
    public List<Double> averageOfLevels(TreeNode root) {

        List<Double> list=new ArrayList<>();
//        int sum=0;

        Deque<TreeNode> queue=new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int size= queue.size();
            //用int极端情况会越界。
            double sum=0;
            for (int i = 0; i < size; i++) {
                TreeNode cur=queue.poll();
                if (cur.left!=null){
                    queue.add(cur.left);
                }
                if (cur.right!=null){
                    queue.add(cur.right);
                }
                sum+=cur.val;
            }
            double avg= sum /size;
            list.add(avg);
        }
        return list;
    }

    //也可以采用深度优先遍历。DFS
    public static List<Double> averageOfLevels1(TreeNode root){
        List<Integer> counts=new ArrayList<>();
        List<Double> sums=new ArrayList<>();
        List<Double> averages=new ArrayList<>();

        dfs(root,0,counts,sums);
        for (int i = 0; i < counts.size(); i++) {
            double temp= sums.get(i)/counts.get(i);
            averages.add(i,temp);

        }
        return averages;

    }
    public static void dfs(TreeNode root,int level,List<Integer> counts,List<Double> sums){
        if (root==null){
            return;
        }
        if (level<sums.size()){
            //累加，更新下标level的值
            sums.set(level, sums.get(level)+ root.val);
            counts.set(level, counts.get(level)+1);
        }else {
            sums.add((double) root.val);
            counts.add(1);
        }
        //遍历左右子树。
        dfs(root.left,level+1,counts,sums);
        dfs(root.right,level+1,counts,sums);
    }
}
